package main.动态规划;

/**
 * @author tmh
 * @date 2024/8/6 19:38
 * @description
 */
public class T322零钱兑换 {
    int[] memo;

    public int coinChange(int[] coins, int amount) {
        //1.边界条件的判断
        if (coins.length == 0) {
            return -1;
        }
        //2.初始化memo数组
        memo = new int[amount];
        return findWay(coins, amount);

    }

    //memo[n]表示钱币n可以换取的最少硬币数，不能换取则为-1
    //定义一个findWay函数：目的是为了找到amount数量的零钱可以兑换的最少硬币的数量，返回值为int
    public int findWay(int[] coins, int amount) {
        //首先进行边界条件的判断
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        //如果memo数组的最后一个元素不为0，那么就直接返回这个值
        if (memo[amount - 1] != 0) {
            return memo[amount - 1];
        }
        //定义一个min来保存结果
        int min = Integer.MAX_VALUE;
        //遍历数组
        for (int i = 0; i < coins.length; i++) {
            //递归遍历
            int res = findWay(coins, amount - coins[i]);
            //条件判断 res
            if (res >= 0 && res < min) {
                //这个+1就理解为，经历了一次递归就+1吧
                min = res + 1;
            }
        }
        //更新memo数组最后一个元素的值
        memo[amount - 1] = min == Integer.MAX_VALUE ? -1 : min;
        return memo[amount - 1];
    }
}
